\section{Experimental Results and Analysis}
\label{sec:pe}
%In this section,
%We conduct an extensive experimental study
%to verify the soundness of our proposed MobiTrack.
%The performance of the MRMU algorithm is evaluated
%by comparing the effects in terms of
%prediction accuracy, system cost, system benefit,
%system utility and task coverage.

\subsection{Effectiveness of Movement Prediction}
\label{subsec:move_pre}
\subsubsection{Location learning}
\begin{figure*}
	%\vspace{-0.8cm}  %璋冩暣鍥剧墖涓庝笂鏂囩殑鍨傜洿璺濈
	  \setlength{\abovecaptionskip}{0.1cm}   % 璋冩暣鍥剧墖鏍囬涓庡浘璺濈
	  \setlength{\belowcaptionskip}{-0.5cm}   % 璋冩暣鍥剧墖鏍囬涓庝笅鏂囪窛绂�
		\centering
		\begin{minipage}[t]{0.33\linewidth}
			\centerline{
			\includegraphics[width=0.95\textwidth]{fig/sp_trend.eps}}
			\centerline{\small{(a) SP Distribution}}
		\end{minipage}%
		\begin{minipage}[t]{0.33\linewidth}
			\centerline{
			\includegraphics[width=0.95\textwidth]{fig/loc_trend.eps}}
			\centerline{\small{(b) Location Distribution}}
		\end{minipage}
		\begin{minipage}[t]{0.33\linewidth}
			\centerline{
			\includegraphics[width=0.80\textwidth]{fig/loc_mark.eps}}
			\centerline{\small{(c) Learned Locations (part)}}
		\end{minipage}
	
	 \caption{Simulations of Location Learning.}
	 \label{fig:loc_lr}
	\end{figure*}
When analyzing the 30 days of GPS data,
we discovered that the number of significant points and the time threshold $\mathbb{T}$
followed a nearly quadratic relationship (shown in Fig.~\ref{fig:loc_lr}(a)).
The knee in the graph happens at $\mathbb{T}_k=60s$,
where 51,5629 significant points were found.
For the reason that the knee signifies the time just before the number of significant points begins to converge,
we determined to take $60s$ as the final time threshold.

Fig.~\ref{fig:loc_lr}(b) shows the number of locations found as cluster radius changes after we keep time threshold as $\mathbb{T}_k$. As the radius $r$ approaches zero, the number of locations grows rapidly. When $r>150m$, a linear relationship between
radius and the number of locations emerged.
Considering that locations clustered from a large radius possibly contain multiple meaningful places,
while a small radius would split one place to several locations, we apply $r=100m$ to extract locations
(at $r = 100m$, 7,049 locations were learned). Fig.~\ref{fig:loc_lr}(c) shows partial learned locations. As expected, meaningful places, e.g., intersection, community and bus stop are marked as locations by using our method.

\subsubsection{Prediction accuracy}
\begin{figure*}
	%\vspace{-0.8cm}  %璋冩暣鍥剧墖涓庝笂鏂囩殑鍨傜洿璺濈
	  \setlength{\abovecaptionskip}{0.1cm}   % 璋冩暣鍥剧墖鏍囬涓庡浘璺濈
	  \setlength{\belowcaptionskip}{-0.5cm}   % 璋冩暣鍥剧墖鏍囬涓庝笅鏂囪窛绂�
		\centering
		\begin{minipage}[t]{0.33\linewidth}
			\centerline{ \includegraphics[width=0.95\textwidth]{fig/n_impact.pdf}}
			\centerline{\small{(a) The Impact of $N$}}
		\end{minipage}
		\begin{minipage}[t]{0.33\linewidth}
			\centerline{
			\includegraphics[width=0.95\textwidth]{fig/pred.pdf}}
			\centerline{\small{(b) Prediction Accuracy}}
		\end{minipage}%
		\begin{minipage}[t]{0.33\linewidth}
			\centerline{ \includegraphics[width=0.95\textwidth]{fig/sensing_loc.pdf}}
			\centerline{\small{(c) Tracking coverage}}
		\end{minipage}
	
	 \caption{Simulations of Movement Prediction.}
	 \label{fig:move_pred}
	\end{figure*}

First of all,
a suitable $N$ needs to be decided
for our training dataset.
We conduct an extensive experimental study
to evaluate the performance of our $N$-Gram-C algorithm
under different value of $N$.
Note that $N$ means the size of the gram.
Fig.~\ref{fig:move_pred}(a)
shows the results obtained by Gram-C with
n ranging from 2 to 5.
The number of trajectories is set to 1000,000.
With the $n$ increasing,
we find that the prediction accuracy
is increasing when $N$ is from 2 to 3,
while its value decreases slightly when n is above 3.
This is because $N=3$ rolls the direction information to help for movement prediction.
However, $N$-Gram-C may suffer from the "data sparsity" problem when $N$ increases.
Therefore, we set $N$ as 3.

% In order to evaluate the effectiveness of our proposed
% $N$-Gram-C model, $N$-MPRE,
% which is a variant of grid-based MMC prediction algorithm
% MPRE~\cite{JingGWLLY18},
% is employed as the baseline.
% Note that $N$ means to
% incorporate the $n$ previous visited grids
% of the object for next movement prediction.
% We set the side length of the grid $g=100$.
Fig.~\ref{fig:move_pred}(b) depicts the prediction accuracy
of the 3-Gram-C and the baseline.
We can observe that
$N$-MPRE also achieves higher prediction accuracy when $N=3$.
As a comparison,
$3$-Gram-C still outperforms the baseline,
which shows around $10.03\%$ and $8.515\%$ on average
under the experiment settings of $N=2$ and $N=3$, respectively.
One possible reason is that the same location
would be divided to different grids in $N$-MPRE
without the consideration of semantic information,
thus degrades the prediction accuracy of grid-based algorithms.
%One possible reason is that vehicles may across different grid
%to the same location.

\subsubsection{Minimal region determination}
We conduct $100,000$ tracking tasks generated from the trajectory dataset
to determine the minimal tracking region. As shown in Fig.~\ref{fig:move_pred}(c),
picking a most probable arrival location by our prediction method
as sensing location can achieve $81.17\%$ tracking coverage
when $P_\zeta=0.6$.
As expected, higher tracking rate requires more sensing locations
to cover the same task numbers.
For $P_\zeta=0.9$, the tracking coverage reaches about 99.38\%
when sensing location number is 4.
Hence, we set the minimal $k=4$.

\subsection{Performance of Task Assignment Strategies}
\label{subsec:effct_task_assign}
% In this subsection, we investigate the system performance
% under different task assignment strategies.
% To scale down the task assignment problem,
% 10 historical ongoing trips ($f$) from the dataset are randomly picked
% to represent 10 tracking tasks.
% By observing from~\ref{fig:move_pred}(d),
% we set the minimal $k=5$.
% The simulation benefit of a tracking task is set to $M=100$.
% Workers arrive in the system proportionally at random
% over the predicted sensing locations,
% and the number of workers is set from 1 to 100.
% Specifically,
% Workers distributes within $r=100m$ around location $l_i$
% with the the probability $p(l_i|f)/\sum_{j=1}^k(p(l_j|f))$.
% To meet the time constraint,
% we simply assume that the average moving speed of workers equals to the object.

% In order to simulate workers' behaviors in real world,
% we use the following benchmarks.
% \begin{itemize}
%   \item \textbf{Nearest Location First (NLF).}
%   NLF is a greedy strategy to select the closest sensing
%   location, which aims to minimize the system cost
%   while ignoring the system benefit.
%   \item \textbf{Most Probable Location First (MPLF).}
%   MPLF is also a greedy strategy but selecting the most possible sensing location with the highest payment.
%   \item \textbf{People-Centric Selection (PCS)~\cite{JingGWLLY18}.}
%   Each worker randomly selects a sensing location within
%   the time constraint, to conduct the tracking task without
%   considering any system performance.
% %  \item \textbf{Most Benefit Nearest Worker Selection (MBNWS).} MBNWS is a greedy strategy to assign the
% %      closest worker to the most possible location, thus
% %      achieve the maximum utility.
% \end{itemize}
\begin{figure*}
	%\vspace{-0.8cm}  %璋冩暣鍥剧墖涓庝笂鏂囩殑鍨傜洿璺濈
	  \setlength{\abovecaptionskip}{0.1cm}   % 璋冩暣鍥剧墖鏍囬涓庡浘璺濈
	  \setlength{\belowcaptionskip}{-0.5cm}   % 璋冩暣鍥剧墖鏍囬涓庝笅鏂囪窛绂�
		\centering
		\begin{minipage}[t]{0.33\linewidth}
			\centerline{
		\includegraphics[width=0.95\textwidth]{fig/sys_cost.eps}}
			\centerline{\small{(a) System Cost}}
		\end{minipage}%
		\begin{minipage}[t]{0.33\linewidth}
			\centerline{
			\includegraphics[width=0.95\textwidth]{fig/sys_bf.eps}}
			\centerline{\small{(b) System Benefit}}
		\end{minipage}
		\begin{minipage}[t]{0.33\linewidth}
			\centerline{
			\includegraphics[width=0.95\textwidth]{fig/sys_uti.eps}}
			\centerline{\small{(c) System Utility}}
		\end{minipage}
		% \begin{minipage}[t]{0.24\linewidth}
		% 	\centerline{
		% 	\includegraphics[width=0.95\textwidth]{fig/cover.eps}}
		%     \centerline{\small{(d) Tracking Coverage}}
		% \end{minipage}
	
	 \caption{Simulations of Different Task Assignment Strategies Under Different Number of Workers.}
	 \label{fig:task_assign_res}
	\end{figure*}



Fig.~\ref{fig:task_assign_res}(a) depicts the system cost of the four strategies.
It is clear that our MUTA approach
achieves the lowest system cost,
followed by NLF.
This is because the greedy-based algorithm
always searches the nearest sensing location for current worker,
leading to some sub-optimal tasks for other workers.
We can also observe that
as workers arrive in the system continually,
the cost of all schemes increases dramatically
when the number of workers is not more than 15,
then drops sharply of MUTA and subtly of three benchmarks.
This phenomenon indicates that
a MCS-based task can be better completed
with more collaborative users roll in.

The system benefit of the schemes is shown in
Fig.~\ref{fig:task_assign_res}(b).
Apparently,
almost all methods could achieve $100\%$ benefit (i.e., 100)
when the number of workers is 9 or more.
However, MPLF have a poor performance
in terms of system benefit
when compared to NLF, PCS, MUTA,
around $27.66\%,30.44\%,30.34\%$ less on average
when the number of workers is no more than 5, respectively.
This shows the sub-optimal problem of greedy algorithms again.


Fig.~\ref{fig:task_assign_res}(c) shows the system utility,
which is the most important metric.
Apparently,
the system utility of our method increases
with growing workers participating in tracking.
Nevertheless,
few improvements are achieved by the rest three benchmarks
since it cannot really help the system
with local greedy-base selection or random selection.
Specifically,
although PCS achieves a little better performance
in terms of the system benefit,
its performance is not well regarding to the system utility.
NLF and MUTA show around $12\%$ and $207\%$
improvements on average over PCS, respectively.
%The result not only reveal insights
%of our approach on the MCS-based tracking system,
%but also guide its practical implementation,
%i.e.,

% Finally, we investigated the tracking coverage
% (i.e., the cover ratio of sensing locations)
% of the schemes,
% and the result is shown in
% Fig.~\ref{fig:task_assign_res}(d).
% We find that NLF achieves the highest coverage,
% followed by MPLF and PCS.
% Our approach gets a subtle lower coverage,
% this explains the reason why MUTA brings lower cost depicts in Fig.~\ref{fig:task_assign_res}(a),
% since fewer sensing locations are assigned with workers
% for tracking tasks.

% \begin{figure}
%% \vspace{-0.8cm}  %璋冩暣鍥剧墖涓庝笂鏂囩殑鍨傜洿璺濈
%  \setlength{\abovecaptionskip}{0.1cm}   % 璋冩暣鍥剧墖鏍囬涓庡浘璺濈
%  \setlength{\belowcaptionskip}{-0.5cm}   % 璋冩暣鍥剧墖鏍囬涓庝笅鏂囪窛绂�
%  \centering{
%  \includegraphics[width=0.30\textwidth]{fig/cover.eps}}
%  \caption{Task Coverage Under Different Number of Candidates.}
%  \label{fig:task_cover}
%\end{figure}
